In a digital processing system, especially for a sequence with finite length, a DFT (Discrete Fourier Transform) is a vitally essential mathematic transform. In nature, it is a discrete sampling of finite points of the Fourier transform of a sequence with finite length. It enables the digital signal processing to be accomplished by employing a digital computation method in the frequency domain, enhancing the flexibility of digital signal processing. The DFT has been broadly applied in the field of digital communication, image processing, power spectrum estimation, etc. Wherein, a computation of DFT with a point number of powers of 2 may be accomplished by employing an algorithm of radix 2 FFT. In the case of other point numbers, namely, the computation could not be accomplished by employing a FFT algorithm, it is referred to as a general number DFT.
Presently, a general number DFT generally employs a mixed radix algorithm on the theoretical basis of Cooley-Tukey algorithm. A radix 2 FFT algorithm is derived by modifying on this basis. Its basic idea is: converting a DFT of larger point number to a plurality of DFTs of smaller point number, wherein each round of computation is referred to as one level, each level of computation is executed sequentially to accomplish the entire process of DFT. Typically, the smaller point number is set to a prime number, i.e. 3, 5, . . . , while in computation, it is proceeded in a nested way sequentially in accordance with radix 3, radix 5, . . . . The radix N operation of each level is executed a number of times, but the data which is specific to varies.X(k)=A+WN/3k×B+WN/32k×B+WN/32k×C X(k+3/N)=A+WNN/3×WN/3k×B+WN2N/3×WN/32k×C X(k+2N/3)=A+WN2N/3×WN/3k×B+WN4N/3×WN/32k×C   (1)
Eq (1) is an expression of a radix 3 algorithm, wherein WN/3k, WN/32k are input twiddle factors, which are relevant to k; and WNN/3, WN2N/3, WN4N/3 are output twiddle factors, which are irrelevant to k;
Since the process of a general number DFT is not an integer multiple of 2, when it is processed by a general processor, the data of an integer group may not be read in or wrote out at once, so that the degree of concurrency is reduced. Moreover, the process of a general DFT processing is first proceeded with a multiplication and an addition computation between the data and the input twiddle factors, and then is proceeded with a multiplication and an addition computation between the data and the output twiddle factors, resulting in a comparably larger relevance between data. Moreover, the process of a general number DFT performs the multiplication computation and the addition computation alternatively, which brings in the relevance of calculation again. This leads to a longer waiting cycle of the arithmetic unit caused by the relevance among data, a lower pipeline usage, and so that the processing speed of the entire computation of DFT is reduced.
To this end, the present application is presented hereby.